package day2_linkedlist.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/2 15:47
 * @Description:分割链表
 * https://leetcode-cn.com/problems/partition-list-lcci/
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
 * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你不需要 保留 每个分区中各节点的初始相对位置。
 */
public class PartitionList {
    // 重新建立两个新的子链表，第一个链表存储所有小于给定值的节点
    // 第二个链表存储大于等于该节点值的节点
    // 拼装两个链表即可，返回小链表的头结点
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null)
            return head;
        ListNode smallList = new ListNode(-1);
        ListNode smallListTail = smallList;
        ListNode bigList = new ListNode(-1);
        ListNode bigListTail = bigList;
        while (head != null) {
            ListNode node = new ListNode(head.val);
            if (head.val < x) {
                // 插入小链表
                smallListTail.next = node;
                smallListTail = node;
            }else {
                bigListTail.next = node;
                bigListTail = node;
            }
            head = head.next;
        }
        smallListTail.next = bigList.next;
        return smallList.next;
    }
}
